//
//  Problem645.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/21.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 645. 错误的集合 简单
 集合 s 包含从 1 到 n 的整数。 不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
 给定一个数组 nums 代表了集合 S 发生错误后的结果。
 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
 示例 1：
     输入：nums = [1,2,2,4]
     输出：[2,3]
 示例 2：
     输入：nums = [1,1]
     输出：[1,2]
 提示：
     2 <= nums.length <= 104
     1 <= nums[i] <= 104
 */
class Problem645: NSObject {
    /*
     方法一：哈希
     遍历数组，找到重复的数字
     */
    func findErrorNums(_ nums: [Int]) -> [Int] {
        var dic:[Int: Int] = [:]
        var a = 0
        var sum = (1 + nums.count) * nums.count / 2
        for n in nums {
            sum -= n
            
            if a == 0 {
                if dic[n] != nil {
                    a = n
                } else {
                    dic[n] = 1
                }
            }
        }
        return [a, sum + a]
    }
    /*
     方法：位运算
        a: 重复数字 b: 缺少数字
     1: 遍历nums: 对每一个数字进行异或，然后在异或i，最后得到就是 xor = a ^ b
     2: lowbit = xor & (-xor) 得到的是只保留xor的二进制中最低一个为1的位数
        2.1 为什么lowbit可以得到这个，例如xor  = 0 1 0 0 1 0 0 0; 那么-xor的求法是：
            第一步：将最高位置1 => 1 1 0 0 1 0 0 0
            第二步：除了最高位，其他位都取反 => 1 0 1 1 0 1 1 1
            第三步：+1 => 1 0 1 1 1 0 0 0
          所以-xor与xor的区别是：最低一个为1的位数相同，其他都是相反
        2.2 xor & (-xor) 得到的就是，只保留最低一个为1的位数，也是xor在该位为1：
            0 1 0 0 1 0 0 0 & 1 0 1 1 1 0 0 0 = 0 0 0 0 1 0 0 0
     3: 因为xor在这一位是1，意味着a和b在这一位是不同的：1 0，但是不知道a是1，还是b是1，所以可以根据他用来区分其他数字：
        遍历nums + i：根据该位 == 1 和 == 0进行区分，然后进行异或，得到的就是2个数字，但是还是不知道来区分这2个数字
     4:
        
     */
    func findErrorNums1(_ nums: [Int]) -> [Int] {
        var xor = 0
        var sum = (1 + nums.count) * nums.count / 2
        for (i, n) in nums.enumerated() {
            sum -= n
            xor ^= n ^ (i + 1)
        }
        
        let lowbit = xor & (-xor)
        var a = 0, b = 0
        for (i, n) in nums.enumerated() {
            if n & lowbit == 0 {
                b ^= n
            } else {
                a ^= n
            }
            if (i + 1) & lowbit == 0 {
                b ^= (i + 1)
            } else {
                a ^= (i + 1)
            }
        }
        
        return b - a == sum ? [a, b] : [b, a]
    }
}
